package main.java;

/**
 * @program: pratice
 * @author: 关键我是大怪
 * @create: 2021-09-09 19:29
 */

/**
 * 题目：
 * 给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j]
 * 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。
 * 如果没有不包含相同字符的一对字符串，返回 0。
 */

public class Test16_单词长度的最大乘积 {

    //暴力解法，直接遍历
    public int maxProduct1(String[] words) {
        int ans = 0;
        for (int i = 0; i < words.length; i++) {
            String word1 = words[i];
            for (int j = i + 1; j < words.length; j++) {
                String word2 = words[j];
                // 每个单词的 bitMask 会重复计算很多次
                if (!hasSameChar1(word1, word2)) {
                    ans = Math.max(ans, word1.length() * word2.length());
                }
            }
        }
        return ans;
    }

    // O(m^2)
    private boolean hasSameChar1(String word1, String word2) {
        for (char c : word1.toCharArray()) {
            if (word2.indexOf(c) != -1) {
                return true;
            }
        }
        return false;
    }


    //int类型有32位 将26个字母全部转换为二进制 ，进行与运算，结果为1说明存在相同

    public int maxProduct(String[] words) {
        int[] arr = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            int a = 0;
            for (int j = 0; j < words[i].length(); j++) {
                a |= (1 << (words[i].charAt(j) - 'a'));
            }
            arr[i] = a;
        }
        int max = 0;
        for (int i = 0; i < words.length - 1; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if ((arr[i] & arr[j]) == 0) {
                    max = Math.max(max, words[i].length() * words[j].length());
                }
            }
        }
        return max;
    }
}
